
class Geld {
	
	static int		c[]			= { 1, 2, 5, 10, 20, 50, 100, 200 };
	static int		N			= c.length;
	static long		cache[][]	= new long[2001][N];
	static boolean	cacheit		= false;
	
	public static int tryParse(String text) {
		try {
			return Integer.parseInt(text);
		} catch (NumberFormatException e) {
			return -1;
		}
	}
	
	public static void main(String[] s) {
		
		int sum = 0;
		int param = s.length;
		
		if (param == 0) {
			System.out.println("Aufruf mit Geldbetrag (in Cent) als Parameter");
			System.out.println("Aufruf: Geld [parameter] Betrag (in Cent, max 2000ct)");
			System.out.println("Parameter -c Cache -m Million -b Milliarde");
			System.exit(-1);
		}
		
		if (s[0].equals("-m")) {
			cacheit = true;
			System.out.println(million());
			System.exit(-1);
		}
		
		if (s[0].equals("-b")) {
			cacheit = true;
			System.out.println(billion());
			System.exit(-1);
		}
		
		if (s[0].equals("-c")) {
			// System.out.println("cache!");
			cacheit = true;
			
			if (param == 1) {
				System.out.println("Aufruf mit Geldbetrag (in Cent) als Parameter");
				System.exit(-1);
			} else {
				sum = tryParse(s[1]);
			}
		} else {
			sum = tryParse(s[0]);
		}
		if ((sum < 1) | (sum > 2000)) {
			System.out.println("Aufruf mit Geldbetrag (in Cent) als Parameter: maximal 2000 cent");
			System.exit(-1);
		}
		
		System.out.print(euro(sum));
		System.out.print(" kann auf ");
		System.out.print(pay(sum));
		System.out.println(" verschiedene Arten passend bezahlt werden");
	}
	
	public static long pay(int m) {
		
		return pay(m, N - 1);
	}
	
	private static long pay(int m, int n) {
		long d1, d2 = 0;
		// System.out.print("(m:" + m + " n:" + n + ")");
		
		if (n == 0) {
			return 1;
		} else {
			if (m < c[n]) {
				if ((cacheit) & (cache[m][n - 1] != 0)) {
					// System.out.print("c(m:" + m + " n:" + n + ")");
					d1 = cache[m][n - 1];
				} else {
					d1 = pay(m, n - 1);
					cache[m][n - 1] = d1;
				}
				return d1;
			} else {
				if ((cacheit) & (cache[m - c[n]][n] != 0)) {
					// System.out.print("c(m:" + m + " n:" + n + ")");
					d1 = cache[m - c[n]][n];
				} else {
					d1 = pay(m - c[n], n);
					cache[m - c[n]][n] = d1;
				}
				if ((cacheit) & (cache[m][n - 1] != 0)) {
					d2 = cache[m][n - 1];
				} else {
					d2 = pay(m, n - 1);
					cache[m][n - 1] = d2;
				}
				return d1 + d2;
			}
		}
	}
	
	public static int minpay(long mp) {
		int r = 1;
		do {
			r++;
		} while (pay(r) < mp);
		return r;
	}
	
	public static String million() {
		return euro(minpay(1000000));
	}
	
	public static String billion() {
		return euro(minpay(1000000000));
	}
	
	public static String euro(int cent) {
		return String.format("%d.%02d Euro", cent / 100, cent % 100);
	}
	
}